|
习该博主「houjingyi233」的贪心算法而感： 原文链接：https://blog.csdn.net/qq_32400847/article/details/51336300
贪心/贪婪算法的主要思想就是局部最优——>全局最优，这并不是一个比较难理解的概念，然后我经过相关的题目案例发现难点在于求得每一个局部最优解的算法。 心算法的定义： 1.活动选择问题： 有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。
#include
#include
struct Act{
int start;
int end;
}act[1000];
/*活动选择问题*/
void sort(Act act[],int n);
int explore(Act act[],int n);
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i
for(int i=0;i
if(act[j].end>act[j+1].end)
{
Act temp=act[j];
act[j]=act[j+1];
act[j+1]=temp;
}
}
}
}
int explore(Act act[],int n)
{
int result=1;
for(int i=0;i
if(act[i].end
int m[7]= {1,2,5,10,20,50,100}; //先有纸币的数额
int k;
//所找的金额
int num; //所需纸币的张数
while(( scanf("%d",&k))!=EOF) {
while(k>0) {
if(k>=100) {
k-=100;
} else if(k>=50&&k
k-=20;
} else if(k>=5&&k
k-=2;
} else if(k>=1&&k //表示每条线段的左右区间的值
int x;
int y;
};
void sort(Line l[],int n); //将每一个区间按照左端点递增的顺序排序
int search(Line l[],int n,int m) ;
int main() {
//m为区间长度，n为线段条数
int m,n;
scanf("%d%d",&m,&n);
Line l[n];
for(int i=0; i
for(int i=0; i
if(l[j].x>l[j+1].x) {
Line temp=l[j];
l[j]=l[j+1];
l[j+1]=temp;
}
}
}
}
int search(Line l[],int n,int m) {
int i=0;
int ans=0,max=0,r=l[0].x;
for(i=0; i
for(int j=i; j
max=l[j].y;
i=j;
}
}
r=max;
max=0;
ans++;
}
if(r>=m) {
break;
}
}
if(r
return ans;
}
}
|